#include<iostream>
#include<vector>
#include<tr1/unordered_map>
using namespace std;
class Solution
{
    // 扔进去AC了他
public:
    //暴力解法
    vector<int> twoSum(vector<int>& nums, int target)
    {
        int n = nums.size();
        vector<int> ans(2,0);
        for(int i=0;i<n;i++)
        {
            int temp=target - nums[i];
            for(int j=i+1;j<n;j++)
            {
                if(nums[j]==temp)
                {   ans[0]=i;
                   ans[1]=j;
                   return ans;}
            }
        };
        return ans;

    };
    vector<int> twoSum2(vector<int>& nums, int target)
    {
        int n = nums.size();
        std::tr1::unordered_map<int, int> hash;
        for(int i = 0; i < n; i++)
        {
        	if(hash.count(target - nums[i]))
        	    return {hash[target - nums[i]], i};
        	hash[nums[i]] = i;
		}
		return {-1, -1};
    }

};


int main() {
    int a[] = {2,7,11,15};
    int k = 9;
    int n = sizeof(a)/sizeof(a[0]);
    vector<int> arr(a,a+n);
    vector<int> ar(2,0);
    ar = Solution().twoSum2(arr,k);
    for(int i=0;i<2;i++)
        cout<<ar[i]<<" ";
    cout<<endl;
    return 0;
}